pub fn dp_rec_mc(amount: u32) -> u32 {
    // package dp, use 2-dimension array to store the result
    const CASHES: [u32; 8] = [1, 2, 5, 10, 20, 30, 50, 100];
    let cashes_len = CASHES.len();
    // dp[i][j]: the least number of cashed that use first i cash to make amount j
    let mut dp = vec![vec![u32::MAX - 100; amount as usize + 1]; cashes_len];
    for j in 0..=amount as usize {
        dp[0][j] = j as u32;
    }
    for i in 1..cashes_len {
        for j in 0..=amount as usize {
            dp[i][j] = dp[i][j].min(dp[i - 1][j]);
            if j + CASHES[i] as usize > amount as usize {
                break;
            }
            dp[i][j + CASHES[i] as usize] = dp[i][j + CASHES[i] as usize].min(dp[i - 1][j] + 1);
        }
    }
    // println!("{:?}", dp);
    // return the min of dp[i][amount]
    dp.iter().map(|v| v[amount as usize]).min().unwrap()
}
